package org.example.SolutionNew002;

import java.util.ArrayList;
import java.util.List;

public class LinkedList03 {
    private ListNode preNode;

    public static void main(String[] args) {
        LinkedList03 linkedList03 = new LinkedList03();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
        System.out.println(linkedList03.isPalindrome(head));
    }

    public boolean isPalindrome1(ListNode head) {
        //翻转，然后同时遍历，若不同则返回false，否则true；
        ListNode reverse = null;
        ListNode newHead=head;
        while (newHead != null) {
            ListNode next = newHead.next;
            ListNode newNode=new ListNode(newHead.val);
            newNode.next = reverse;
            reverse = newNode;
            newHead = next;
        }
        while (head != null&&reverse!=null) {
            if (head.val != reverse.val) {
                return false;
            }
            head = head.next;
            reverse = reverse.next;
        }
        return true;
    }

    //双指针
    public boolean isPalindrome2(ListNode head) {
        List<Integer> list=new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        int start=0,end=list.size()-1;
        while(start<end){
            if(list.get(start)!=list.get(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    //递归
    public boolean isPalindrome3(ListNode head) {
        preNode=head;
        return reverseAndCompare(head);
    }

    public boolean reverseAndCompare(ListNode head){
        if(head!=null){
            if(!reverseAndCompare(head.next)){
                return false;
            }
            if(preNode.val!=head.val){
                return false;
            }
            preNode=preNode.next;
        }
        return true;
    }



    //快慢指针
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;

        ListNode midNode=findFirstPart(head);
        ListNode afterNode=reversePart(midNode.next);

        boolean res=true;
        while(res&&afterNode!=null){
            if(afterNode.val!=head.val){
                res=false;
            }
            afterNode=afterNode.next;
            head=head.next;
        }
        midNode.next=reversePart(afterNode);
        return res;
    }

    public ListNode findFirstPart(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    public ListNode reversePart(ListNode head){
        ListNode prev=null;
        ListNode nextHead;
        while(head!=null){
            nextHead=head.next;
            head.next=prev;
            prev=head;
            head=nextHead;
        }
        return prev;
    }
}

